package com.linyaonan.leetcode.sword_to_offer._24;

import java.util.LinkedList;

/**
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 *
 *  
 *
 * 示例:
 *
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 *  
 *
 * 限制：
 *
 * 0 <= 节点个数 <= 5000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    /**
     * 简单做法：使用栈的结构记录链表的原始数据，然后创建新链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        // 异常情况
        if (head == null || head.next == null) {
            return head;
        }

        LinkedList<Integer> list = new LinkedList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        ListNode listNode = new ListNode(-1);
        ListNode h = listNode;
        while (!list.isEmpty()) {
            listNode.next = new ListNode(list.removeLast());
            listNode = listNode.next;
        }
        return h.next;

    }

    public ListNode reverseList2(ListNode head) {
        // 异常情况
        if (head == null || head.next == null) {
            return head;
        }

        ListNode result = null;

        while (head != null) {
            ListNode ap = new ListNode(head.val);
            ap.next = result;
            result = ap;
            head = head.next;
        }

        return result;

    }
}